Recommender Systems: Minichallenge 2 HS23

library(recommenderlab)
library(tidyverse)
library(ggplot2)

7 Content-based Recommender System

7.1 Erzeugung von Film- & Nutzerprofilen

7.1.1. MovieLense Daten einlesen

data("MovieLense") 

user_item_ratings <- as(MovieLense, "data.frame")
user_df <- MovieLenseUser
movie_genre_df <- MovieLenseMeta

7.1.2 Binäre User-Liked_Items Matrix für alle Nutzer erzeugen

user_item_ratings <- user_item_ratings %>% 
  mutate(user = as.factor(user), item = as.factor(item), rating = as.integer(rating))
library(reshape2)

# Transformation der Ratings in binäre Werte
user_item_ratings$binarizedRating <- as.integer(ifelse(user_item_ratings$rating > 3, 1, 0))

# Erstellen der User-Liked-Items Matrix
user_liked_df <- dcast(user_item_ratings, user ~ item, value.var = "binarizedRating", fill = 0)

# Anzeigen der erstellten Matrix
print(user_liked_df)

Da es nun noch ein DF ist werde ich das in eine Matrix umwandeln und die User IDs als Index verwenden.

# user_liked_matrix as matrix machen und user IDs als index nehmen
user_liked_matrix <- as.matrix(user_liked_df[,-1])
rownames(user_liked_matrix) <- user_liked_df[,1]

7.1.3 Dimension der User-Liked-Items Matrix prüfen und ausgeben

dim(user_liked_matrix)
[1]  943 1664

Die Dimensionen der user_liked_matrix machen Sinn, da die Anzahl der User mit der Anzahl der Zeilen und die Anzahl der Items mit der Anzahl der Spalten übereinstimmt.

7.1.4 Movie-Genre Matrix für alle Filme erzeugen

# Setzen der Filmnamen als Zeilenindex
rownames(movie_genre_df) <- movie_genre_df[,1]

# Nur die ersten 3 Spalten Titel, Jahr und URL löschen und nur die Genres behalten
movie_genre_df_reduced <- movie_genre_df[,-c(1,2,3)]

# df umwandeln in eine Matrix
movie_genre_matrix <- as.matrix(movie_genre_df_reduced)

7.1.5 Dimension der Movie-Genre Matrix prüfen und ausgeben

dim(movie_genre_matrix)
[1] 1664   19

Die Dimensionen der Matrix machen ebenfalls Sinn. Die Anzahl der Filme stimmt mit der Anzahl Zeilen überein. Auch alle 19 Genres sind in den Spalten enthalten.

7.1.6 Anzahl unterschiedlicher Filmprofile bestimmen und visualisieren

# Erstellen einer Genre-Kombinations-Spalte
genre_combinations <- apply(movie_genre_matrix[, -1], 1, function(x) paste(names(x)[x == 1], collapse = ", "))

# Zählen der Häufigkeiten der Genre-Kombinationen
genre_combination_counts <- table(genre_combinations)

# Umwandeln in einen DataFrame
genre_combination_df <- as.data.frame(genre_combination_counts)

# Sortieren und Top 29 auswählen
top_genre_combinations <- genre_combination_df[order(-genre_combination_df$Freq), ][1:29, ]

# Hinzufügen der Kategorie "Others combined"
others_combined <- sum(genre_combination_df$Freq) - sum(top_genre_combinations$Freq)
top_genre_combinations <- rbind(top_genre_combinations, data.frame(genre_combinations = "Others combined", Freq = others_combined))


# Gesamtanzahl der Kombinationen
total_combinations <- length(genre_combination_counts)

# Identifizieren der größten Genre-Kombination
max_freq <- max(top_genre_combinations$Freq)
top_genre_combinations$Color <- ifelse(top_genre_combinations$Freq == max_freq, "orchid", "skyblue")

# Visualisierung mit ggplot2
ggplot(top_genre_combinations, aes(x = genre_combinations, y = Freq, fill = Color)) +
  geom_bar(stat = "identity") +
  coord_flip() +
  scale_fill_identity() +
  labs(title = "Verteilung der Filme nach Genre-Kombination", subtitle = paste("Top 30 Genre-Kombinationen von insgesamt: ", total_combinations), x = "Genre-Kombination", y = "Anzahl der Filme") +
  theme_minimal()

Others combined wäre die am häufigsten vorkommende Genre-Kombination, wenn es denn eine wäre. Das tatsächlich häfuigste Genre ist Drama, gefolgt von Comedy. Diese drei Genre-Kombinationen machen zusammen den Grossteil aller Genrekombinationen von den Top 30 aus. Ich finde es sehr interessant zu sehen, dass das Genre Drama insgesammt fast so häufig vertreten ist wie alle “Others Combined” Kombinationen.

7.1.7 Nutzerprofile im Genre-Vektorraum erzeugen

# sortiere movie_genre_matrix nach Titel absteigend, damit es zur Berechnung geht.
movie_genre_matrix <- movie_genre_matrix[order(rownames(movie_genre_matrix), decreasing = FALSE), ]
# Matrixmultiplikation
user_genre_profile_matrix <- user_liked_matrix %*% movie_genre_matrix

# Anzeigen der ersten Nutzerprofile
head(user_genre_profile_matrix)
    unknown Action Adventure Animation Children's Comedy Crime Documentary Drama Fantasy
1         1     39        17         5          5     49    15           5    77       1
10        0     25        14         7          8     39    16           3    73       1
100       0      6         1         0          0      4     2           0    11       0
101       0      9         7         0          0      4     1           0     4       0
102       0     10         6         3          2      6     1           0     4       0
103       0      8         4         0          0      4     3           0     5       0
    Film-Noir Horror Musical Mystery Romance Sci-Fi Thriller War Western
1           1      7       6       3      29     32       30  15       3
10          9      6      13      15      32     11       33  19       5
100         2      0       0       2       3      3        9   2       0
101         0      1       0       1       7      4        5   3       0
102         1      5       4       1       3     11        4   1       1
103         0      0       0       0       4      4        3   3       0

7.1.8 Dimension der User-Genre-Profil Matrix prüfen und ausgeben

dim(user_genre_profile_matrix)
[1] 943  19

Die Dimensionen der Matrix machen Sinn. Die Anzahl der User stimmt mit der Anzahl der Zeilen überein. Auch alle 19 Genres sind in den Spalten enthalten.

7.1.9 Anzahln unterschiedlicher Nutzerprofile bestimmen, wenn Stärke der Genre-Kombination (a) vollständig (b) binär berücksichtigt wird.

a.) wieviele Nutzerprofile gibt es wenn die Stärke der Genre-Kombination vollständig berücksichtigt wird?

# Länge der unique Userprofiles ausgeben mit aktuellen Werten
length(unique(apply(user_genre_profile_matrix, 1, paste, collapse = ", ")))
[1] 943

b.) Wieviele Nutzerprofile gibt es wenn die Stärke der Genre-Kombination binär berücksichtigt wird?

# Länge der unique Userprofiles ausgeben für 1, falls 1 oder höher und 0 sonst
length(unique(apply(user_genre_profile_matrix > 0, 1, paste, collapse = ", ")))
[1] 381

7.2 Ähnlichkeit von Nutzern und Filmen [10 Punkte]

7.2.1 Cosinus-Ähnlichkeit zwischen User-Genre- und Movie-Genre-Matrix berechnen.

calc_cos_similarity_twomtrx <- function(matrix_1, matrix_2) {
  # Berechnung der Normen für beide Matrizen
  norms_matrix_1 <- sqrt(rowSums(matrix_1^2))
  norms_matrix_2 <- sqrt(rowSums(matrix_2^2))

  # Berechnung des äußeren Produkts der Normen
  norm_product <- outer(norms_matrix_1, norms_matrix_2, "*")

  # Berechnung der Cosinus-Ähnlichkeit
  cosine_similarity <- (matrix_1 %*% t(matrix_2)) / norm_product
  
  return(cosine_similarity)
}
# Erstellen von Testmatrizen
matrix_1 <- matrix(c(1,0,2,1,1,0), nrow = 2, ncol = 3, byrow = TRUE)
matrix_2 <- matrix(c(1,1,1,0,1,0), nrow = 2, ncol = 3, byrow = TRUE)

# Funktion mit kleinen Matrizen testen
cos_similarity_eigeneMatrix <- calc_cos_similarity_twomtrx(matrix_1, matrix_2)

# Ausgabe
print(cos_similarity_eigeneMatrix)
          [,1]      [,2]
[1,] 0.7745967 0.0000000
[2,] 0.8164966 0.7071068

Das Resultat habe ich schriftlich geprüft und bin auf das gleiche Resultat gekommen. Somit kann ich bestätigen, dass die Berechnungen für die Cosine-Similarity funktionieren. Daher kann ich nun die Cosinusähnlichkeiten für die Matrizen user_genre_profile_matirx und movie_genre_matrix berechnen.

# Cosinus-Ähnlichkeit zwischen User-Genre- und Movie-Genre-Matrix berechnen
cosine_similarity_matrix <- calc_cos_similarity_twomtrx(user_genre_profile_matrix, movie_genre_matrix)

# erste 5 Zeilen und Spalten ausgeben
cosine_similarity_matrix[1:5, 1:5]
    'Til There Was You (1997) 1-900 (1994) 101 Dalmatians (1996) 12 Angry Men (1957)
1                   0.6442370    0.2492601             0.3281962           0.6618286
10                  0.7021566    0.3026284             0.3142987           0.6903710
100                 0.5823232    0.1764706             0.1663781           0.6470588
101                 0.4787136    0.4308202             0.1740777           0.2461830
102                 0.2496817    0.1513300             0.2853506           0.2017733
    187 (1997)
1    0.6618286
10   0.6903710
100  0.6470588
101  0.2461830
102  0.2017733

7.2.2 Dimension der Matrix der Cosinus-Ähnlichkeiten von Nutzern und Filmen prüfen uns ausgeben.

dim(cosine_similarity_matrix)
[1]  943 1664

Die Dimension stimmt wieder mit der Anzahl der User und der Anzahl der Filme überein. Dies sollte so sein, da die Cosinus-Ähnlichkeit zwischen User-Genre- und Movie-Genre-Matrix berechnet wurde.

7.2.3 5-Zahlen Statistik für Matrix der Cosinus-Ähnlichkeiten prüfen uns ausgeben.

# Konvertierung der Matrix in einen Vektor
cos_similarity_vector <- as.vector(cosine_similarity_matrix)

# Berechnung der 5-Zahlen-Statistik
min_value <- min(cos_similarity_vector, na.rm = TRUE)
first_quartile <- quantile(cos_similarity_vector, 0.25, na.rm = TRUE)
median_value <- median(cos_similarity_vector, na.rm = TRUE)
third_quartile <- quantile(cos_similarity_vector, 0.75, na.rm = TRUE)
max_value <- max(cos_similarity_vector, na.rm = TRUE)

# Berechnung des Mittelwerts
mean_value <- mean(cos_similarity_vector, na.rm = TRUE)

# Berechnung der Anzahl von NAs
na_count <- sum(is.na(cos_similarity_vector))

# Ausgabe der Statistiken
cat("5-Zahlen-Statistik der Cosinus-Ähnlichkeiten:\n",
    "Minimum:", min_value, "\n",
    "1. Quartil:", first_quartile, "\n",
    "Median:", median_value, "\n",
    "3. Quartil:", third_quartile, "\n",
    "Maximum:", max_value, "\n",
    "Mittelwert:", mean_value, "\n",
    "Anzahl von NAs:", na_count, "\n")
5-Zahlen-Statistik der Cosinus-Ähnlichkeiten:
 Minimum: 0 
 1. Quartil: 0.2300219 
 Median: 0.4070324 
 3. Quartil: 0.5919163 
 Maximum: 0.9767817 
 Mittelwert: 0.4098111 
 Anzahl von NAs: 1664 

In diesem Code:

Die Matrix wird zuerst in einen Vektor konvertiert, um die Berechnungen zu vereinfachen. Die Funktionen min(), quantile(), median() und max() werden verwendet, um die entsprechenden Statistiken zu berechnen, wobei na.rm = TRUE angibt, dass NA-Werte ignoriert werden sollen. Der Mittelwert wird mit mean() berechnet, ebenfalls unter Ausschluss von NA-Werten. sum(is.na()) zählt die Anzahl der NA-Werte in dem Vektor.

7.2.4 Cosinus-Ähnlichkeiten von Nutzern und Filmen mit Dichteplot visualisieren

# NA-Werte entfernen aus dem Vektor
cos_similarity_vector <- cos_similarity_vector[!is.na(cos_similarity_vector)]

# Erstellen eines DataFrames für die ggplot2 Funktion
cos_similarity_df <- data.frame(CosineSimilarity = cos_similarity_vector)

# Erstellen des Dichteplots
ggplot(cos_similarity_df, aes(x = CosineSimilarity)) +
  geom_density(fill = "orchid", alpha = 0.4) +
  labs(title = "Dichteplot der Cosinus-Ähnlichkeiten",
       x = "Cosinus-Ähnlichkeit",
       y = "Dichte") +
  theme_minimal()

7.2.5 Cosinus-Ähnlichkeiten von Nutzern und Filmen mit Dichteplot für Nutzer “241”, “414”, “477”, “526”, “640” und “710” visualisieren.

user_ids <- c("241", "414", "477", "526", "640", "710")

# Erstellen eines DataFrames für die ggplot2 Funktion
cos_similarity_long_df <- data.frame(CosineSimilarity = numeric(), User = factor())

# Extrahieren der Cosinus-Ähnlichkeitswerte für jeden Nutzer und Hinzufügen zum DataFrame
for (user_id in user_ids) {
  user_similarity <- cosine_similarity_matrix[user_id, ]
  user_similarity <- user_similarity[!is.na(user_similarity)]  # Entfernen von NA-Werten
  cos_similarity_long_df <- rbind(cos_similarity_long_df, data.frame(CosineSimilarity = user_similarity, User = as.factor(user_id)))
}

# Erstellen des Dichteplots mit unterschiedlichen Farben für jeden Nutzer
ggplot(cos_similarity_long_df, aes(x = CosineSimilarity, fill = User)) +
  geom_density(alpha = 0.5) +
  facet_wrap(~ User, ncol = 2) +
  labs(title = "Dichteplot der Cosinus-Ähnlichkeiten für ausgewählte Nutzer",
       x = "Cosinus-Ähnlichkeit",
       y = "Dichte") +
  theme_minimal() +
  scale_fill_brewer(palette = "Set1")  # Verwenden einer voreingestellten Farbpalette

Verteilungen der Cosinus-Ähnlichkeiten für die ausgewählten Nutzer Erklären.

7.3 Empfehlbare Filme [6 Punkte]

7.3.1 Bewertete Filme maskieren, d.h. “Negativabzug” der User-Items Matrix erzeugen, um anschliessend Empfehlungen herzuleiten.

Um die Negativabzug Matrix zu erstellen brauche ich zuerst den Dataframe, in dem ersichtlich ist, welche Filme von welchen Nutzern bewertet wurden. Dabei ist zu beachten, dass die Filme, welche nicht bewertet wurden, mit 0 angegeben werden.

# Date Frame erstellen mit User und Filmen, welche ein Rating haben = 1. Sonst = 0
user_watched_df <- dcast(user_item_ratings, user ~ item, value.var = "rating", fill = 0)

# where there is a rating, set it to 1 where not set to 0 exept first col
user_watched_df[, -1] <- ifelse(user_watched_df[, -1] > 0, 1, 0)

Nun kann ich die Negativabzug Matrix erstellen. Dabei wird die Matrix mit 0 initialisiert und dann mit einer ifelse Funktion die Werte, welche 0 sind, auf 1 gesetzt und umgekehrt.

# Filme, die nicht bewertet wurden (0), werden zu 1, und bewertete Filme (1) werden zu 0, ausser 1. spalte bleibt gleich
negativabzug_matrix <- user_watched_df
negativabzug_matrix[, -1] <- ifelse(negativabzug_matrix[, -1] == 0, 1, 0)

7.3.2 Zeilensumme des “Negativabzuges” der User-Items Matrix für die User “5”, “25”, “50” und “150” aus- geben

# Ausgewählte Nutzer-IDs
selected_users <- c("5", "25", "50", "150")

# Berechnung der Zeilensummen für die ausgewählten Nutzer
for (user in selected_users) {
  user_row_sum <- sum(negativabzug_matrix[negativabzug_matrix$user == user, -1])
  cat("Zeilensumme des Negativabzuges für Nutzer", user, ":", user_row_sum, "\n")
}
Zeilensumme des Negativabzuges für Nutzer 5 : 1489 
Zeilensumme des Negativabzuges für Nutzer 25 : 1586 
Zeilensumme des Negativabzuges für Nutzer 50 : 1641 
Zeilensumme des Negativabzuges für Nutzer 150 : 1633 

7.3.3 5-Zahlen Statistik der Zeilensumme des “Negativabzuges” der User-Items Matrix bestimmen.

# Berechnung der Zeilensummen
zeilensummen <- rowSums(negativabzug_matrix[, -1])

# Berechnung der 5-Zahlen-Statistik
min_value <- min(zeilensummen)
erstes_quartil <- quantile(zeilensummen, 0.25)
median_value <- median(zeilensummen)
drittes_quartil <- quantile(zeilensummen, 0.75)
max_value <- max(zeilensummen)

# Ausgabe der 5-Zahlen-Statistik
cat("5-Zahlen-Statistik der Zeilensummen des Negativabzuges:\n",
    "Minimum:", min_value, "\n",
    "1. Quartil:", erstes_quartil, "\n",
    "Median:", median_value, "\n",
    "3. Quartil:", drittes_quartil, "\n",
    "Maximum:", max_value, "\n")
5-Zahlen-Statistik der Zeilensummen des Negativabzuges:
 Minimum: 929 
 1. Quartil: 1516.5 
 Median: 1600 
 3. Quartil: 1632 
 Maximum: 1645 

7.4 Top-N Empfehlungen [12 Punkte]

7.4.1. Matrix für Bewertung aller Filme durch element-weise Multiplikation der Matrix der Cosinus- Ähnlichkeiten von Nutzern und Filmen und “Negativabzug” der User-Items Matrix erzeugen

# rownames of negativabzug_matrix are the user ids
rownames(negativabzug_matrix) <- negativabzug_matrix$user

# drop user column
negativabzug_matrix <- negativabzug_matrix[, -1]
masked_df <- cosine_similarity_matrix * negativabzug_matrix
masked_df

7.4.2 Dimension der Matrix für die Bewertung aller Filme prüfen.

#masked_df zu matrix umwandeln$
masked_matrix <- as.matrix(masked_df)
dim(masked_matrix)
[1]  943 1664

7.4.3 Top-20 Listen extrahieren und Länge der Listen pro Nutzer prüfen.

get_topn_recos <- function(bewertungsmatrix, N = 20) {
  top_n_recos <- lapply(1:nrow(bewertungsmatrix), function(row_index) {
    row <- bewertungsmatrix[row_index, ]
    sorted_indices <- order(row, decreasing = TRUE)
    top_n_indices <- head(sorted_indices, N)
    names(row)[top_n_indices]
  })
  names(top_n_recos) <- rownames(bewertungsmatrix)
  return(top_n_recos)
}
# Anwenden der Funktion, um die Top-20 Empfehlungen für jeden Nutzer zu erhalten
top_20_recos <- get_topn_recos(masked_matrix, N = 20)

# Berechnung der Länge der Empfehlungslisten für jeden Nutzer
listen_laengen <- sapply(top_20_recos, length)

# Berechnung der 5-Zahlen-Statistik für die Listenlängen
min_listen_laenge <- min(listen_laengen)
erstes_quartil <- quantile(listen_laengen, 0.25)
median_listen_laenge <- median(listen_laengen)
drittes_quartil <- quantile(listen_laengen, 0.75)
max_listen_laenge <- max(listen_laengen)

# Ausgabe der 5-Zahlen-Statistik
cat("5-Zahlen-Statistik der Längen der Top-20 Empfehlungslisten:\n",
    "Minimum:", min_listen_laenge, "\n",
    "1. Quartil:", erstes_quartil, "\n",
    "Median:", median_listen_laenge, "\n",
    "3. Quartil:", drittes_quartil, "\n",
    "Maximum:", max_listen_laenge, "\n")
5-Zahlen-Statistik der Längen der Top-20 Empfehlungslisten:
 Minimum: 20 
 1. Quartil: 20 
 Median: 20 
 3. Quartil: 20 
 Maximum: 20 

7.4.4 Verteilung der minimalen Ähnlichkeit für Top-N Listen für N = 10, 20, 50, 100 für alle Nutzer visuell vergleichen.

7.4.5 Top-20 Empfehlungen für Nutzer “5”, “25”, “50”, “150” visualisieren

7.4.6 Für Nutzer “133” und “555” Profil mit Top-N Empfehlungen für N = 20, 30, 40, 50 analysieren, visualisieren und diskutieren

Verwendung von KI-Tools

In dieser Challenge wurde teilweise auf KI-Tools zurückgegriffen. Diese sind im Folgenden aufgelistet: Github Copilot zu unterstützung von schnellerem und effizienterem Programmieren Chat-GPT zum erläutern von Konzepten und zur Hilfe für Code generieren. `

LS0tCnRpdGxlOiAiSFMyM19SU1lfTUMyX1plbXBMdWthcyIKb3V0cHV0OiBodG1sX25vdGVib29rCi0tLQoKIyBSZWNvbW1lbmRlciBTeXN0ZW1zOiBNaW5pY2hhbGxlbmdlIDIgSFMyMwoKYGBge3J9CmxpYnJhcnkocmVjb21tZW5kZXJsYWIpCmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KGdncGxvdDIpCmBgYAojIDcgQ29udGVudC1iYXNlZCBSZWNvbW1lbmRlciBTeXN0ZW0KCiMjIDcuMSBFcnpldWd1bmcgdm9uIEZpbG0tICYgTnV0emVycHJvZmlsZW4KCiMjIyA3LjEuMS4gTW92aWVMZW5zZSBEYXRlbiBlaW5sZXNlbgoKYGBge3J9CmRhdGEoIk1vdmllTGVuc2UiKSAKCnVzZXJfaXRlbV9yYXRpbmdzIDwtIGFzKE1vdmllTGVuc2UsICJkYXRhLmZyYW1lIikKdXNlcl9kZiA8LSBNb3ZpZUxlbnNlVXNlcgptb3ZpZV9nZW5yZV9kZiA8LSBNb3ZpZUxlbnNlTWV0YQpgYGAKCiMjIyA3LjEuMiBCaW7DpHJlIFVzZXItTGlrZWRfSXRlbXMgTWF0cml4IGbDvHIgYWxsZSBOdXR6ZXIgZXJ6ZXVnZW4KYGBge3J9CnVzZXJfaXRlbV9yYXRpbmdzIDwtIHVzZXJfaXRlbV9yYXRpbmdzICU+JSAKICBtdXRhdGUodXNlciA9IGFzLmZhY3Rvcih1c2VyKSwgaXRlbSA9IGFzLmZhY3RvcihpdGVtKSwgcmF0aW5nID0gYXMuaW50ZWdlcihyYXRpbmcpKQpgYGAKCmBgYHtyfQpsaWJyYXJ5KHJlc2hhcGUyKQoKIyBUcmFuc2Zvcm1hdGlvbiBkZXIgUmF0aW5ncyBpbiBiaW7DpHJlIFdlcnRlCnVzZXJfaXRlbV9yYXRpbmdzJGJpbmFyaXplZFJhdGluZyA8LSBhcy5pbnRlZ2VyKGlmZWxzZSh1c2VyX2l0ZW1fcmF0aW5ncyRyYXRpbmcgPiAzLCAxLCAwKSkKCiMgRXJzdGVsbGVuIGRlciBVc2VyLUxpa2VkLUl0ZW1zIE1hdHJpeAp1c2VyX2xpa2VkX2RmIDwtIGRjYXN0KHVzZXJfaXRlbV9yYXRpbmdzLCB1c2VyIH4gaXRlbSwgdmFsdWUudmFyID0gImJpbmFyaXplZFJhdGluZyIsIGZpbGwgPSAwKQoKIyBBbnplaWdlbiBkZXIgZXJzdGVsbHRlbiBNYXRyaXgKcHJpbnQodXNlcl9saWtlZF9kZikKYGBgCkRhIGVzIG51biBub2NoIGVpbiBERiBpc3Qgd2VyZGUgaWNoIGRhcyBpbiBlaW5lIE1hdHJpeCB1bXdhbmRlbG4gdW5kIGRpZSBVc2VyIElEcyBhbHMgSW5kZXggdmVyd2VuZGVuLiAKCgpgYGB7cn0KIyB1c2VyX2xpa2VkX21hdHJpeCBhcyBtYXRyaXggbWFjaGVuIHVuZCB1c2VyIElEcyBhbHMgaW5kZXggbmVobWVuCnVzZXJfbGlrZWRfbWF0cml4IDwtIGFzLm1hdHJpeCh1c2VyX2xpa2VkX2RmWywtMV0pCnJvd25hbWVzKHVzZXJfbGlrZWRfbWF0cml4KSA8LSB1c2VyX2xpa2VkX2RmWywxXQpgYGAKCgojIyMgNy4xLjMgRGltZW5zaW9uIGRlciBVc2VyLUxpa2VkLUl0ZW1zIE1hdHJpeCBwcnXMiGZlbiB1bmQgYXVzZ2ViZW4KYGBge3J9CmRpbSh1c2VyX2xpa2VkX21hdHJpeCkKYGBgCgpEaWUgRGltZW5zaW9uZW4gZGVyIHVzZXJfbGlrZWRfbWF0cml4IG1hY2hlbiBTaW5uLCBkYSBkaWUgQW56YWhsIGRlciBVc2VyIG1pdCBkZXIgQW56YWhsIGRlciBaZWlsZW4gdW5kIGRpZSBBbnphaGwgZGVyIEl0ZW1zIG1pdCBkZXIgQW56YWhsIGRlciBTcGFsdGVuIMO8YmVyZWluc3RpbW10LgoKCiMjIyA3LjEuNCBNb3ZpZS1HZW5yZSBNYXRyaXggZnXMiHIgYWxsZSBGaWxtZSBlcnpldWdlbgpgYGB7cn0KIyBTZXR6ZW4gZGVyIEZpbG1uYW1lbiBhbHMgWmVpbGVuaW5kZXgKcm93bmFtZXMobW92aWVfZ2VucmVfZGYpIDwtIG1vdmllX2dlbnJlX2RmWywxXQoKIyBOdXIgZGllIGVyc3RlbiAzIFNwYWx0ZW4gVGl0ZWwsIEphaHIgdW5kIFVSTCBsw7ZzY2hlbiB1bmQgbnVyIGRpZSBHZW5yZXMgYmVoYWx0ZW4KbW92aWVfZ2VucmVfZGZfcmVkdWNlZCA8LSBtb3ZpZV9nZW5yZV9kZlssLWMoMSwyLDMpXQoKIyBkZiB1bXdhbmRlbG4gaW4gZWluZSBNYXRyaXgKbW92aWVfZ2VucmVfbWF0cml4IDwtIGFzLm1hdHJpeChtb3ZpZV9nZW5yZV9kZl9yZWR1Y2VkKQpgYGAKCgojIyMgNy4xLjUgRGltZW5zaW9uIGRlciBNb3ZpZS1HZW5yZSBNYXRyaXggcHJ1zIhmZW4gdW5kIGF1c2dlYmVuCmBgYHtyfQpkaW0obW92aWVfZ2VucmVfbWF0cml4KQpgYGAKRGllIERpbWVuc2lvbmVuIGRlciBNYXRyaXggbWFjaGVuIGViZW5mYWxscyBTaW5uLiBEaWUgQW56YWhsIGRlciBGaWxtZSBzdGltbXQgbWl0IGRlciBBbnphaGwgWmVpbGVuIMO8YmVyZWluLiBBdWNoIGFsbGUgMTkgR2VucmVzIHNpbmQgaW4gZGVuIFNwYWx0ZW4gZW50aGFsdGVuLgoKIyMjIDcuMS42ICBBbnphaGwgdW50ZXJzY2hpZWRsaWNoZXIgRmlsbXByb2ZpbGUgYmVzdGltbWVuIHVuZCB2aXN1YWxpc2llcmVuCmBgYHtyfQojIEVyc3RlbGxlbiBlaW5lciBHZW5yZS1Lb21iaW5hdGlvbnMtU3BhbHRlCmdlbnJlX2NvbWJpbmF0aW9ucyA8LSBhcHBseShtb3ZpZV9nZW5yZV9tYXRyaXhbLCAtMV0sIDEsIGZ1bmN0aW9uKHgpIHBhc3RlKG5hbWVzKHgpW3ggPT0gMV0sIGNvbGxhcHNlID0gIiwgIikpCgojIFrDpGhsZW4gZGVyIEjDpHVmaWdrZWl0ZW4gZGVyIEdlbnJlLUtvbWJpbmF0aW9uZW4KZ2VucmVfY29tYmluYXRpb25fY291bnRzIDwtIHRhYmxlKGdlbnJlX2NvbWJpbmF0aW9ucykKCiMgVW13YW5kZWxuIGluIGVpbmVuIERhdGFGcmFtZQpnZW5yZV9jb21iaW5hdGlvbl9kZiA8LSBhcy5kYXRhLmZyYW1lKGdlbnJlX2NvbWJpbmF0aW9uX2NvdW50cykKCiMgU29ydGllcmVuIHVuZCBUb3AgMjkgYXVzd8OkaGxlbgp0b3BfZ2VucmVfY29tYmluYXRpb25zIDwtIGdlbnJlX2NvbWJpbmF0aW9uX2RmW29yZGVyKC1nZW5yZV9jb21iaW5hdGlvbl9kZiRGcmVxKSwgXVsxOjI5LCBdCgojIEhpbnp1ZsO8Z2VuIGRlciBLYXRlZ29yaWUgIk90aGVycyBjb21iaW5lZCIKb3RoZXJzX2NvbWJpbmVkIDwtIHN1bShnZW5yZV9jb21iaW5hdGlvbl9kZiRGcmVxKSAtIHN1bSh0b3BfZ2VucmVfY29tYmluYXRpb25zJEZyZXEpCnRvcF9nZW5yZV9jb21iaW5hdGlvbnMgPC0gcmJpbmQodG9wX2dlbnJlX2NvbWJpbmF0aW9ucywgZGF0YS5mcmFtZShnZW5yZV9jb21iaW5hdGlvbnMgPSAiT3RoZXJzIGNvbWJpbmVkIiwgRnJlcSA9IG90aGVyc19jb21iaW5lZCkpCgoKIyBHZXNhbXRhbnphaGwgZGVyIEtvbWJpbmF0aW9uZW4KdG90YWxfY29tYmluYXRpb25zIDwtIGxlbmd0aChnZW5yZV9jb21iaW5hdGlvbl9jb3VudHMpCgojIElkZW50aWZpemllcmVuIGRlciBncsO2w590ZW4gR2VucmUtS29tYmluYXRpb24KbWF4X2ZyZXEgPC0gbWF4KHRvcF9nZW5yZV9jb21iaW5hdGlvbnMkRnJlcSkKdG9wX2dlbnJlX2NvbWJpbmF0aW9ucyRDb2xvciA8LSBpZmVsc2UodG9wX2dlbnJlX2NvbWJpbmF0aW9ucyRGcmVxID09IG1heF9mcmVxLCAib3JjaGlkIiwgInNreWJsdWUiKQoKIyBWaXN1YWxpc2llcnVuZyBtaXQgZ2dwbG90MgpnZ3Bsb3QodG9wX2dlbnJlX2NvbWJpbmF0aW9ucywgYWVzKHggPSBnZW5yZV9jb21iaW5hdGlvbnMsIHkgPSBGcmVxLCBmaWxsID0gQ29sb3IpKSArCiAgZ2VvbV9iYXIoc3RhdCA9ICJpZGVudGl0eSIpICsKICBjb29yZF9mbGlwKCkgKwogIHNjYWxlX2ZpbGxfaWRlbnRpdHkoKSArCiAgbGFicyh0aXRsZSA9ICJWZXJ0ZWlsdW5nIGRlciBGaWxtZSBuYWNoIEdlbnJlLUtvbWJpbmF0aW9uIiwgc3VidGl0bGUgPSBwYXN0ZSgiVG9wIDMwIEdlbnJlLUtvbWJpbmF0aW9uZW4gdm9uIGluc2dlc2FtdDogIiwgdG90YWxfY29tYmluYXRpb25zKSwgeCA9ICJHZW5yZS1Lb21iaW5hdGlvbiIsIHkgPSAiQW56YWhsIGRlciBGaWxtZSIpICsKICB0aGVtZV9taW5pbWFsKCkKYGBgCk90aGVycyBjb21iaW5lZCB3w6RyZSBkaWUgYW0gaMOkdWZpZ3N0ZW4gdm9ya29tbWVuZGUgR2VucmUtS29tYmluYXRpb24sIHdlbm4gZXMgZGVubiBlaW5lIHfDpHJlLiBEYXMgdGF0c8OkY2hsaWNoIGjDpGZ1aWdzdGUgR2VucmUgaXN0IERyYW1hLCBnZWZvbGd0IHZvbiBDb21lZHkuIERpZXNlIGRyZWkgR2VucmUtS29tYmluYXRpb25lbiBtYWNoZW4genVzYW1tZW4gZGVuIEdyb3NzdGVpbCBhbGxlciBHZW5yZWtvbWJpbmF0aW9uZW4gdm9uIGRlbiBUb3AgMzAgYXVzLiBJY2ggZmluZGUgZXMgc2VociBpbnRlcmVzc2FudCB6dSBzZWhlbiwgZGFzcyBkYXMgR2VucmUgRHJhbWEgaW5zZ2VzYW1tdCBmYXN0IHNvIGjDpHVmaWcgdmVydHJldGVuIGlzdCB3aWUgYWxsZSAiT3RoZXJzIENvbWJpbmVkIiBLb21iaW5hdGlvbmVuLiAKCiMjIyA3LjEuNyBOdXR6ZXJwcm9maWxlIGltIEdlbnJlLVZla3RvcnJhdW0gZXJ6ZXVnZW4KCmBgYHtyfQojIHNvcnRpZXJlIG1vdmllX2dlbnJlX21hdHJpeCBuYWNoIFRpdGVsIGFic3RlaWdlbmQsIGRhbWl0IGVzIHp1ciBCZXJlY2hudW5nIGdlaHQuCm1vdmllX2dlbnJlX21hdHJpeCA8LSBtb3ZpZV9nZW5yZV9tYXRyaXhbb3JkZXIocm93bmFtZXMobW92aWVfZ2VucmVfbWF0cml4KSwgZGVjcmVhc2luZyA9IEZBTFNFKSwgXQojIE1hdHJpeG11bHRpcGxpa2F0aW9uCnVzZXJfZ2VucmVfcHJvZmlsZV9tYXRyaXggPC0gdXNlcl9saWtlZF9tYXRyaXggJSolIG1vdmllX2dlbnJlX21hdHJpeAoKIyBBbnplaWdlbiBkZXIgZXJzdGVuIE51dHplcnByb2ZpbGUKaGVhZCh1c2VyX2dlbnJlX3Byb2ZpbGVfbWF0cml4KQpgYGAKCgojIyMgNy4xLjggRGltZW5zaW9uIGRlciBVc2VyLUdlbnJlLVByb2ZpbCBNYXRyaXggcHJ1zIhmZW4gdW5kIGF1c2dlYmVuCgpgYGB7cn0KZGltKHVzZXJfZ2VucmVfcHJvZmlsZV9tYXRyaXgpCmBgYApEaWUgRGltZW5zaW9uZW4gZGVyIE1hdHJpeCBtYWNoZW4gU2lubi4gRGllIEFuemFobCBkZXIgVXNlciBzdGltbXQgbWl0IGRlciBBbnphaGwgZGVyIFplaWxlbiDDvGJlcmVpbi4gQXVjaCBhbGxlIDE5IEdlbnJlcyBzaW5kIGluIGRlbiBTcGFsdGVuIGVudGhhbHRlbi4gCgojIyMgNy4xLjkgQW56YWhsbiB1bnRlcnNjaGllZGxpY2hlciBOdXR6ZXJwcm9maWxlIGJlc3RpbW1lbiwgd2VubiBTdGHMiHJrZSBkZXIgR2VucmUtS29tYmluYXRpb24gKGEpIHZvbGxzdGHMiG5kaWcgKGIpIGJpbmHMiHIgYmVydcyIY2tzaWNodGlndCB3aXJkLgoKYS4pIHdpZXZpZWxlIE51dHplcnByb2ZpbGUgZ2lidCBlcyB3ZW5uIGRpZSBTdMOkcmtlIGRlciBHZW5yZS1Lb21iaW5hdGlvbiB2b2xsc3TDpG5kaWcgYmVyw7xja3NpY2h0aWd0IHdpcmQ/CgpgYGB7cn0KIyBMw6RuZ2UgZGVyIHVuaXF1ZSBVc2VycHJvZmlsZXMgYXVzZ2ViZW4gbWl0IGFrdHVlbGxlbiBXZXJ0ZW4KbGVuZ3RoKHVuaXF1ZShhcHBseSh1c2VyX2dlbnJlX3Byb2ZpbGVfbWF0cml4LCAxLCBwYXN0ZSwgY29sbGFwc2UgPSAiLCAiKSkpCgpgYGAKCmIuKSBXaWV2aWVsZSBOdXR6ZXJwcm9maWxlIGdpYnQgZXMgd2VubiBkaWUgU3TDpHJrZSBkZXIgR2VucmUtS29tYmluYXRpb24gYmluw6RyIGJlcsO8Y2tzaWNodGlndCB3aXJkPwpgYGB7cn0KIyBMw6RuZ2UgZGVyIHVuaXF1ZSBVc2VycHJvZmlsZXMgYXVzZ2ViZW4gZsO8ciAxLCBmYWxscyAxIG9kZXIgaMO2aGVyIHVuZCAwIHNvbnN0Cmxlbmd0aCh1bmlxdWUoYXBwbHkodXNlcl9nZW5yZV9wcm9maWxlX21hdHJpeCA+IDAsIDEsIHBhc3RlLCBjb2xsYXBzZSA9ICIsICIpKSkKYGBgCgoKIyMgNy4yIEHMiGhubGljaGtlaXQgdm9uIE51dHplcm4gdW5kIEZpbG1lbiBbMTAgUHVua3RlXQoKIyMjIDcuMi4xIENvc2ludXMtQcyIaG5saWNoa2VpdCB6d2lzY2hlbiBVc2VyLUdlbnJlLSB1bmQgTW92aWUtR2VucmUtTWF0cml4IGJlcmVjaG5lbi4KYGBge3J9CmNhbGNfY29zX3NpbWlsYXJpdHlfdHdvbXRyeCA8LSBmdW5jdGlvbihtYXRyaXhfMSwgbWF0cml4XzIpIHsKICAjIEJlcmVjaG51bmcgZGVyIE5vcm1lbiBmw7xyIGJlaWRlIE1hdHJpemVuCiAgbm9ybXNfbWF0cml4XzEgPC0gc3FydChyb3dTdW1zKG1hdHJpeF8xXjIpKQogIG5vcm1zX21hdHJpeF8yIDwtIHNxcnQocm93U3VtcyhtYXRyaXhfMl4yKSkKCiAgIyBCZXJlY2hudW5nIGRlcyDDpHXDn2VyZW4gUHJvZHVrdHMgZGVyIE5vcm1lbgogIG5vcm1fcHJvZHVjdCA8LSBvdXRlcihub3Jtc19tYXRyaXhfMSwgbm9ybXNfbWF0cml4XzIsICIqIikKCiAgIyBCZXJlY2hudW5nIGRlciBDb3NpbnVzLcOEaG5saWNoa2VpdAogIGNvc2luZV9zaW1pbGFyaXR5IDwtIChtYXRyaXhfMSAlKiUgdChtYXRyaXhfMikpIC8gbm9ybV9wcm9kdWN0CiAgCiAgcmV0dXJuKGNvc2luZV9zaW1pbGFyaXR5KQp9CmBgYAoKYGBge3J9CiMgRXJzdGVsbGVuIHZvbiBUZXN0bWF0cml6ZW4KbWF0cml4XzEgPC0gbWF0cml4KGMoMSwwLDIsMSwxLDApLCBucm93ID0gMiwgbmNvbCA9IDMsIGJ5cm93ID0gVFJVRSkKbWF0cml4XzIgPC0gbWF0cml4KGMoMSwxLDEsMCwxLDApLCBucm93ID0gMiwgbmNvbCA9IDMsIGJ5cm93ID0gVFJVRSkKCiMgRnVua3Rpb24gbWl0IGtsZWluZW4gTWF0cml6ZW4gdGVzdGVuCmNvc19zaW1pbGFyaXR5X2VpZ2VuZU1hdHJpeCA8LSBjYWxjX2Nvc19zaW1pbGFyaXR5X3R3b210cngobWF0cml4XzEsIG1hdHJpeF8yKQoKIyBBdXNnYWJlCnByaW50KGNvc19zaW1pbGFyaXR5X2VpZ2VuZU1hdHJpeCkKYGBgCgpEYXMgUmVzdWx0YXQgaGFiZSBpY2ggc2NocmlmdGxpY2ggZ2VwcsO8ZnQgdW5kIGJpbiBhdWYgZGFzIGdsZWljaGUgUmVzdWx0YXQgZ2Vrb21tZW4uIFNvbWl0IGthbm4gaWNoIGJlc3TDpHRpZ2VuLCBkYXNzIGRpZSBCZXJlY2hudW5nZW4gZsO8ciBkaWUgQ29zaW5lLVNpbWlsYXJpdHkgZnVua3Rpb25pZXJlbi4gRGFoZXIga2FubiBpY2ggbnVuIGRpZSBDb3NpbnVzw6RobmxpY2hrZWl0ZW4gZsO8ciBkaWUgTWF0cml6ZW4gdXNlcl9nZW5yZV9wcm9maWxlX21hdGlyeCB1bmQgbW92aWVfZ2VucmVfbWF0cml4IGJlcmVjaG5lbi4gCgpgYGB7cn0KIyBDb3NpbnVzLcOEaG5saWNoa2VpdCB6d2lzY2hlbiBVc2VyLUdlbnJlLSB1bmQgTW92aWUtR2VucmUtTWF0cml4IGJlcmVjaG5lbgpjb3NpbmVfc2ltaWxhcml0eV9tYXRyaXggPC0gY2FsY19jb3Nfc2ltaWxhcml0eV90d29tdHJ4KHVzZXJfZ2VucmVfcHJvZmlsZV9tYXRyaXgsIG1vdmllX2dlbnJlX21hdHJpeCkKCiMgZXJzdGUgNSBaZWlsZW4gdW5kIFNwYWx0ZW4gYXVzZ2ViZW4KY29zaW5lX3NpbWlsYXJpdHlfbWF0cml4WzE6NSwgMTo1XQpgYGAKCiMjIyA3LjIuMiBEaW1lbnNpb24gZGVyIE1hdHJpeCBkZXIgQ29zaW51cy1BzIhobmxpY2hrZWl0ZW4gdm9uIE51dHplcm4gdW5kIEZpbG1lbiBwcnXMiGZlbiB1bnMgYXVzZ2ViZW4uCgpgYGB7cn0KZGltKGNvc2luZV9zaW1pbGFyaXR5X21hdHJpeCkKYGBgCkRpZSBEaW1lbnNpb24gc3RpbW10IHdpZWRlciBtaXQgZGVyIEFuemFobCBkZXIgVXNlciB1bmQgZGVyIEFuemFobCBkZXIgRmlsbWUgw7xiZXJlaW4uIERpZXMgc29sbHRlIHNvIHNlaW4sIGRhIGRpZSBDb3NpbnVzLcOEaG5saWNoa2VpdCB6d2lzY2hlbiBVc2VyLUdlbnJlLSB1bmQgTW92aWUtR2VucmUtTWF0cml4IGJlcmVjaG5ldCB3dXJkZS4gCgoKIyMjIDcuMi4zICA1LVphaGxlbiBTdGF0aXN0aWsgZnXMiHIgTWF0cml4IGRlciBDb3NpbnVzLUHMiGhubGljaGtlaXRlbiBwcnXMiGZlbiB1bnMgYXVzZ2ViZW4uCgpgYGB7cn0KIyBLb252ZXJ0aWVydW5nIGRlciBNYXRyaXggaW4gZWluZW4gVmVrdG9yCmNvc19zaW1pbGFyaXR5X3ZlY3RvciA8LSBhcy52ZWN0b3IoY29zaW5lX3NpbWlsYXJpdHlfbWF0cml4KQoKIyBCZXJlY2hudW5nIGRlciA1LVphaGxlbi1TdGF0aXN0aWsKbWluX3ZhbHVlIDwtIG1pbihjb3Nfc2ltaWxhcml0eV92ZWN0b3IsIG5hLnJtID0gVFJVRSkKZmlyc3RfcXVhcnRpbGUgPC0gcXVhbnRpbGUoY29zX3NpbWlsYXJpdHlfdmVjdG9yLCAwLjI1LCBuYS5ybSA9IFRSVUUpCm1lZGlhbl92YWx1ZSA8LSBtZWRpYW4oY29zX3NpbWlsYXJpdHlfdmVjdG9yLCBuYS5ybSA9IFRSVUUpCnRoaXJkX3F1YXJ0aWxlIDwtIHF1YW50aWxlKGNvc19zaW1pbGFyaXR5X3ZlY3RvciwgMC43NSwgbmEucm0gPSBUUlVFKQptYXhfdmFsdWUgPC0gbWF4KGNvc19zaW1pbGFyaXR5X3ZlY3RvciwgbmEucm0gPSBUUlVFKQoKIyBCZXJlY2hudW5nIGRlcyBNaXR0ZWx3ZXJ0cwptZWFuX3ZhbHVlIDwtIG1lYW4oY29zX3NpbWlsYXJpdHlfdmVjdG9yLCBuYS5ybSA9IFRSVUUpCgojIEJlcmVjaG51bmcgZGVyIEFuemFobCB2b24gTkFzCm5hX2NvdW50IDwtIHN1bShpcy5uYShjb3Nfc2ltaWxhcml0eV92ZWN0b3IpKQoKIyBBdXNnYWJlIGRlciBTdGF0aXN0aWtlbgpjYXQoIjUtWmFobGVuLVN0YXRpc3RpayBkZXIgQ29zaW51cy3DhGhubGljaGtlaXRlbjpcbiIsCiAgICAiTWluaW11bToiLCBtaW5fdmFsdWUsICJcbiIsCiAgICAiMS4gUXVhcnRpbDoiLCBmaXJzdF9xdWFydGlsZSwgIlxuIiwKICAgICJNZWRpYW46IiwgbWVkaWFuX3ZhbHVlLCAiXG4iLAogICAgIjMuIFF1YXJ0aWw6IiwgdGhpcmRfcXVhcnRpbGUsICJcbiIsCiAgICAiTWF4aW11bToiLCBtYXhfdmFsdWUsICJcbiIsCiAgICAiTWl0dGVsd2VydDoiLCBtZWFuX3ZhbHVlLCAiXG4iLAogICAgIkFuemFobCB2b24gTkFzOiIsIG5hX2NvdW50LCAiXG4iKQoKYGBgCkluIGRpZXNlbSBDb2RlOgoKRGllIE1hdHJpeCB3aXJkIHp1ZXJzdCBpbiBlaW5lbiBWZWt0b3Iga29udmVydGllcnQsIHVtIGRpZSBCZXJlY2hudW5nZW4genUgdmVyZWluZmFjaGVuLgpEaWUgRnVua3Rpb25lbiBtaW4oKSwgcXVhbnRpbGUoKSwgbWVkaWFuKCkgdW5kIG1heCgpIHdlcmRlbiB2ZXJ3ZW5kZXQsIHVtIGRpZSBlbnRzcHJlY2hlbmRlbiBTdGF0aXN0aWtlbiB6dSBiZXJlY2huZW4sIHdvYmVpIG5hLnJtID0gVFJVRSBhbmdpYnQsIGRhc3MgTkEtV2VydGUgaWdub3JpZXJ0IHdlcmRlbiBzb2xsZW4uCkRlciBNaXR0ZWx3ZXJ0IHdpcmQgbWl0IG1lYW4oKSBiZXJlY2huZXQsIGViZW5mYWxscyB1bnRlciBBdXNzY2hsdXNzIHZvbiBOQS1XZXJ0ZW4uCnN1bShpcy5uYSgpKSB6w6RobHQgZGllIEFuemFobCBkZXIgTkEtV2VydGUgaW4gZGVtIFZla3Rvci4KCgoKIyMjIDcuMi40IENvc2ludXMtQcyIaG5saWNoa2VpdGVuIHZvbiBOdXR6ZXJuIHVuZCBGaWxtZW4gbWl0IERpY2h0ZXBsb3QgdmlzdWFsaXNpZXJlbgpgYGB7cn0KIyBOQS1XZXJ0ZSBlbnRmZXJuZW4gYXVzIGRlbSBWZWt0b3IKY29zX3NpbWlsYXJpdHlfdmVjdG9yIDwtIGNvc19zaW1pbGFyaXR5X3ZlY3RvclshaXMubmEoY29zX3NpbWlsYXJpdHlfdmVjdG9yKV0KCiMgRXJzdGVsbGVuIGVpbmVzIERhdGFGcmFtZXMgZsO8ciBkaWUgZ2dwbG90MiBGdW5rdGlvbgpjb3Nfc2ltaWxhcml0eV9kZiA8LSBkYXRhLmZyYW1lKENvc2luZVNpbWlsYXJpdHkgPSBjb3Nfc2ltaWxhcml0eV92ZWN0b3IpCgojIEVyc3RlbGxlbiBkZXMgRGljaHRlcGxvdHMKZ2dwbG90KGNvc19zaW1pbGFyaXR5X2RmLCBhZXMoeCA9IENvc2luZVNpbWlsYXJpdHkpKSArCiAgZ2VvbV9kZW5zaXR5KGZpbGwgPSAib3JjaGlkIiwgYWxwaGEgPSAwLjQpICsKICBsYWJzKHRpdGxlID0gIkRpY2h0ZXBsb3QgZGVyIENvc2ludXMtw4RobmxpY2hrZWl0ZW4iLAogICAgICAgeCA9ICJDb3NpbnVzLcOEaG5saWNoa2VpdCIsCiAgICAgICB5ID0gIkRpY2h0ZSIpICsKICB0aGVtZV9taW5pbWFsKCkKYGBgCgoKIyMjIDcuMi41IENvc2ludXMtQcyIaG5saWNoa2VpdGVuIHZvbiBOdXR6ZXJuIHVuZCBGaWxtZW4gbWl0IERpY2h0ZXBsb3QgZnXMiHIgTnV0emVyIOKAnDI0MeKAnSwg4oCcNDE04oCdLCDigJw0NzfigJ0sIOKAnDUyNuKAnSwgIjY0MOKAnSB1bmQg4oCcNzEw4oCdIHZpc3VhbGlzaWVyZW4uCgpgYGB7cn0KdXNlcl9pZHMgPC0gYygiMjQxIiwgIjQxNCIsICI0NzciLCAiNTI2IiwgIjY0MCIsICI3MTAiKQoKIyBFcnN0ZWxsZW4gZWluZXMgRGF0YUZyYW1lcyBmw7xyIGRpZSBnZ3Bsb3QyIEZ1bmt0aW9uCmNvc19zaW1pbGFyaXR5X2xvbmdfZGYgPC0gZGF0YS5mcmFtZShDb3NpbmVTaW1pbGFyaXR5ID0gbnVtZXJpYygpLCBVc2VyID0gZmFjdG9yKCkpCgojIEV4dHJhaGllcmVuIGRlciBDb3NpbnVzLcOEaG5saWNoa2VpdHN3ZXJ0ZSBmw7xyIGplZGVuIE51dHplciB1bmQgSGluenVmw7xnZW4genVtIERhdGFGcmFtZQpmb3IgKHVzZXJfaWQgaW4gdXNlcl9pZHMpIHsKICB1c2VyX3NpbWlsYXJpdHkgPC0gY29zaW5lX3NpbWlsYXJpdHlfbWF0cml4W3VzZXJfaWQsIF0KICB1c2VyX3NpbWlsYXJpdHkgPC0gdXNlcl9zaW1pbGFyaXR5WyFpcy5uYSh1c2VyX3NpbWlsYXJpdHkpXSAgIyBFbnRmZXJuZW4gdm9uIE5BLVdlcnRlbgogIGNvc19zaW1pbGFyaXR5X2xvbmdfZGYgPC0gcmJpbmQoY29zX3NpbWlsYXJpdHlfbG9uZ19kZiwgZGF0YS5mcmFtZShDb3NpbmVTaW1pbGFyaXR5ID0gdXNlcl9zaW1pbGFyaXR5LCBVc2VyID0gYXMuZmFjdG9yKHVzZXJfaWQpKSkKfQoKIyBFcnN0ZWxsZW4gZGVzIERpY2h0ZXBsb3RzIG1pdCB1bnRlcnNjaGllZGxpY2hlbiBGYXJiZW4gZsO8ciBqZWRlbiBOdXR6ZXIKZ2dwbG90KGNvc19zaW1pbGFyaXR5X2xvbmdfZGYsIGFlcyh4ID0gQ29zaW5lU2ltaWxhcml0eSwgZmlsbCA9IFVzZXIpKSArCiAgZ2VvbV9kZW5zaXR5KGFscGhhID0gMC41KSArCiAgZmFjZXRfd3JhcCh+IFVzZXIsIG5jb2wgPSAyKSArCiAgbGFicyh0aXRsZSA9ICJEaWNodGVwbG90IGRlciBDb3NpbnVzLcOEaG5saWNoa2VpdGVuIGbDvHIgYXVzZ2V3w6RobHRlIE51dHplciIsCiAgICAgICB4ID0gIkNvc2ludXMtw4RobmxpY2hrZWl0IiwKICAgICAgIHkgPSAiRGljaHRlIikgKwogIHRoZW1lX21pbmltYWwoKSArCiAgc2NhbGVfZmlsbF9icmV3ZXIocGFsZXR0ZSA9ICJTZXQxIikgICMgVmVyd2VuZGVuIGVpbmVyIHZvcmVpbmdlc3RlbGx0ZW4gRmFyYnBhbGV0dGUKYGBgClZlcnRlaWx1bmdlbiBkZXIgQ29zaW51cy3DhGhubGljaGtlaXRlbiBmw7xyIGRpZSBhdXNnZXfDpGhsdGVuIE51dHplciBFcmtsw6RyZW4uIAoKCgojIyA3LjMgRW1wZmVobGJhcmUgRmlsbWUgWzYgUHVua3RlXQoKIyMjIDcuMy4xIEJld2VydGV0ZSBGaWxtZSBtYXNraWVyZW4sIGQuaC4g4oCcTmVnYXRpdmFienVn4oCdIGRlciBVc2VyLUl0ZW1zIE1hdHJpeCBlcnpldWdlbiwgdW0gYW5zY2hsaWVzc2VuZCBFbXBmZWhsdW5nZW4gaGVyenVsZWl0ZW4uCgpVbSBkaWUgTmVnYXRpdmFienVnIE1hdHJpeCB6dSBlcnN0ZWxsZW4gYnJhdWNoZSBpY2ggenVlcnN0IGRlbiBEYXRhZnJhbWUsIGluIGRlbSBlcnNpY2h0bGljaCBpc3QsIHdlbGNoZSBGaWxtZSB2b24gd2VsY2hlbiBOdXR6ZXJuIGJld2VydGV0IHd1cmRlbi4gRGFiZWkgaXN0IHp1IGJlYWNodGVuLCBkYXNzIGRpZSBGaWxtZSwgd2VsY2hlIG5pY2h0IGJld2VydGV0IHd1cmRlbiwgbWl0IDAgYW5nZWdlYmVuIHdlcmRlbi4gCmBgYHtyfQojIERhdGUgRnJhbWUgZXJzdGVsbGVuIG1pdCBVc2VyIHVuZCBGaWxtZW4sIHdlbGNoZSBlaW4gUmF0aW5nIGhhYmVuID0gMS4gU29uc3QgPSAwCnVzZXJfd2F0Y2hlZF9kZiA8LSBkY2FzdCh1c2VyX2l0ZW1fcmF0aW5ncywgdXNlciB+IGl0ZW0sIHZhbHVlLnZhciA9ICJyYXRpbmciLCBmaWxsID0gMCkKCiMgd2hlcmUgdGhlcmUgaXMgYSByYXRpbmcsIHNldCBpdCB0byAxIHdoZXJlIG5vdCBzZXQgdG8gMCBleGVwdCBmaXJzdCBjb2wKdXNlcl93YXRjaGVkX2RmWywgLTFdIDwtIGlmZWxzZSh1c2VyX3dhdGNoZWRfZGZbLCAtMV0gPiAwLCAxLCAwKQpgYGAKCk51biBrYW5uIGljaCBkaWUgTmVnYXRpdmFienVnIE1hdHJpeCBlcnN0ZWxsZW4uIERhYmVpIHdpcmQgZGllIE1hdHJpeCBtaXQgMCBpbml0aWFsaXNpZXJ0IHVuZCBkYW5uIG1pdCBlaW5lciBpZmVsc2UgRnVua3Rpb24gZGllIFdlcnRlLCB3ZWxjaGUgMCBzaW5kLCBhdWYgMSBnZXNldHp0IHVuZCB1bWdla2VocnQuIAoKYGBge3J9ICAgIAojIEZpbG1lLCBkaWUgbmljaHQgYmV3ZXJ0ZXQgd3VyZGVuICgwKSwgd2VyZGVuIHp1IDEsIHVuZCBiZXdlcnRldGUgRmlsbWUgKDEpIHdlcmRlbiB6dSAwLCBhdXNzZXIgMS4gc3BhbHRlIGJsZWlidCBnbGVpY2gKbmVnYXRpdmFienVnX21hdHJpeCA8LSB1c2VyX3dhdGNoZWRfZGYKbmVnYXRpdmFienVnX21hdHJpeFssIC0xXSA8LSBpZmVsc2UobmVnYXRpdmFienVnX21hdHJpeFssIC0xXSA9PSAwLCAxLCAwKQpgYGAKCgojIyMgNy4zLjIgWmVpbGVuc3VtbWUgZGVzIOKAnE5lZ2F0aXZhYnp1Z2Vz4oCdIGRlciBVc2VyLUl0ZW1zIE1hdHJpeCBmdcyIciBkaWUgVXNlciDigJw14oCdLCDigJwyNeKAnSwg4oCcNTDigJ0gdW5kIOKAnDE1MOKAnSBhdXMtIGdlYmVuCmBgYHtyfQojIEF1c2dld8OkaGx0ZSBOdXR6ZXItSURzCnNlbGVjdGVkX3VzZXJzIDwtIGMoIjUiLCAiMjUiLCAiNTAiLCAiMTUwIikKCiMgQmVyZWNobnVuZyBkZXIgWmVpbGVuc3VtbWVuIGbDvHIgZGllIGF1c2dld8OkaGx0ZW4gTnV0emVyCmZvciAodXNlciBpbiBzZWxlY3RlZF91c2VycykgewogIHVzZXJfcm93X3N1bSA8LSBzdW0obmVnYXRpdmFienVnX21hdHJpeFtuZWdhdGl2YWJ6dWdfbWF0cml4JHVzZXIgPT0gdXNlciwgLTFdKQogIGNhdCgiWmVpbGVuc3VtbWUgZGVzIE5lZ2F0aXZhYnp1Z2VzIGbDvHIgTnV0emVyIiwgdXNlciwgIjoiLCB1c2VyX3Jvd19zdW0sICJcbiIpCn0KYGBgCgojIyMgNy4zLjMgNS1aYWhsZW4gU3RhdGlzdGlrIGRlciBaZWlsZW5zdW1tZSBkZXMg4oCcTmVnYXRpdmFienVnZXPigJ0gZGVyIFVzZXItSXRlbXMgTWF0cml4IGJlc3RpbW1lbi4KYGBge3J9CiMgQmVyZWNobnVuZyBkZXIgWmVpbGVuc3VtbWVuCnplaWxlbnN1bW1lbiA8LSByb3dTdW1zKG5lZ2F0aXZhYnp1Z19tYXRyaXhbLCAtMV0pCgojIEJlcmVjaG51bmcgZGVyIDUtWmFobGVuLVN0YXRpc3RpawptaW5fdmFsdWUgPC0gbWluKHplaWxlbnN1bW1lbikKZXJzdGVzX3F1YXJ0aWwgPC0gcXVhbnRpbGUoemVpbGVuc3VtbWVuLCAwLjI1KQptZWRpYW5fdmFsdWUgPC0gbWVkaWFuKHplaWxlbnN1bW1lbikKZHJpdHRlc19xdWFydGlsIDwtIHF1YW50aWxlKHplaWxlbnN1bW1lbiwgMC43NSkKbWF4X3ZhbHVlIDwtIG1heCh6ZWlsZW5zdW1tZW4pCgojIEF1c2dhYmUgZGVyIDUtWmFobGVuLVN0YXRpc3RpawpjYXQoIjUtWmFobGVuLVN0YXRpc3RpayBkZXIgWmVpbGVuc3VtbWVuIGRlcyBOZWdhdGl2YWJ6dWdlczpcbiIsCiAgICAiTWluaW11bToiLCBtaW5fdmFsdWUsICJcbiIsCiAgICAiMS4gUXVhcnRpbDoiLCBlcnN0ZXNfcXVhcnRpbCwgIlxuIiwKICAgICJNZWRpYW46IiwgbWVkaWFuX3ZhbHVlLCAiXG4iLAogICAgIjMuIFF1YXJ0aWw6IiwgZHJpdHRlc19xdWFydGlsLCAiXG4iLAogICAgIk1heGltdW06IiwgbWF4X3ZhbHVlLCAiXG4iKQpgYGAKCgojIyA3LjQgVG9wLU4gRW1wZmVobHVuZ2VuIFsxMiBQdW5rdGVdCgojIyMgNy40LjEuIE1hdHJpeCBmdcyIciBCZXdlcnR1bmcgYWxsZXIgRmlsbWUgZHVyY2ggZWxlbWVudC13ZWlzZSBNdWx0aXBsaWthdGlvbiBkZXIgTWF0cml4IGRlciBDb3NpbnVzLSBBzIhobmxpY2hrZWl0ZW4gdm9uIE51dHplcm4gdW5kIEZpbG1lbiB1bmQg4oCcTmVnYXRpdmFienVn4oCdIGRlciBVc2VyLUl0ZW1zIE1hdHJpeCBlcnpldWdlbgoKYGBge3J9CiMgcm93bmFtZXMgb2YgbmVnYXRpdmFienVnX21hdHJpeCBhcmUgdGhlIHVzZXIgaWRzCnJvd25hbWVzKG5lZ2F0aXZhYnp1Z19tYXRyaXgpIDwtIG5lZ2F0aXZhYnp1Z19tYXRyaXgkdXNlcgoKIyBkcm9wIHVzZXIgY29sdW1uCm5lZ2F0aXZhYnp1Z19tYXRyaXggPC0gbmVnYXRpdmFienVnX21hdHJpeFssIC0xXQpgYGAKCmBgYHtyfQptYXNrZWRfZGYgPC0gY29zaW5lX3NpbWlsYXJpdHlfbWF0cml4ICogbmVnYXRpdmFienVnX21hdHJpeAptYXNrZWRfZGYKYGBgCgojIyMgNy40LjIgRGltZW5zaW9uIGRlciBNYXRyaXggZnXMiHIgZGllIEJld2VydHVuZyBhbGxlciBGaWxtZSBwcnXMiGZlbi4KCmBgYHtyfQojbWFza2VkX2RmIHp1IG1hdHJpeCB1bXdhbmRlbG4kCm1hc2tlZF9tYXRyaXggPC0gYXMubWF0cml4KG1hc2tlZF9kZikKYGBgCgoKYGBge3J9CmRpbShtYXNrZWRfbWF0cml4KQpgYGAKCiMjIyA3LjQuMyBUb3AtMjAgTGlzdGVuIGV4dHJhaGllcmVuIHVuZCBMYcyIbmdlIGRlciBMaXN0ZW4gcHJvIE51dHplciBwcnXMiGZlbi4KYGBge3J9CmdldF90b3BuX3JlY29zIDwtIGZ1bmN0aW9uKGJld2VydHVuZ3NtYXRyaXgsIE4gPSAyMCkgewogIHRvcF9uX3JlY29zIDwtIGxhcHBseSgxOm5yb3coYmV3ZXJ0dW5nc21hdHJpeCksIGZ1bmN0aW9uKHJvd19pbmRleCkgewogICAgcm93IDwtIGJld2VydHVuZ3NtYXRyaXhbcm93X2luZGV4LCBdCiAgICBzb3J0ZWRfaW5kaWNlcyA8LSBvcmRlcihyb3csIGRlY3JlYXNpbmcgPSBUUlVFKQogICAgdG9wX25faW5kaWNlcyA8LSBoZWFkKHNvcnRlZF9pbmRpY2VzLCBOKQogICAgbmFtZXMocm93KVt0b3Bfbl9pbmRpY2VzXQogIH0pCiAgbmFtZXModG9wX25fcmVjb3MpIDwtIHJvd25hbWVzKGJld2VydHVuZ3NtYXRyaXgpCiAgcmV0dXJuKHRvcF9uX3JlY29zKQp9CmBgYAoKCmBgYHtyfQojIEFud2VuZGVuIGRlciBGdW5rdGlvbiwgdW0gZGllIFRvcC0yMCBFbXBmZWhsdW5nZW4gZsO8ciBqZWRlbiBOdXR6ZXIgenUgZXJoYWx0ZW4KdG9wXzIwX3JlY29zIDwtIGdldF90b3BuX3JlY29zKG1hc2tlZF9tYXRyaXgsIE4gPSAyMCkKCiMgQmVyZWNobnVuZyBkZXIgTMOkbmdlIGRlciBFbXBmZWhsdW5nc2xpc3RlbiBmw7xyIGplZGVuIE51dHplcgpsaXN0ZW5fbGFlbmdlbiA8LSBzYXBwbHkodG9wXzIwX3JlY29zLCBsZW5ndGgpCgojIEJlcmVjaG51bmcgZGVyIDUtWmFobGVuLVN0YXRpc3RpayBmw7xyIGRpZSBMaXN0ZW5sw6RuZ2VuCm1pbl9saXN0ZW5fbGFlbmdlIDwtIG1pbihsaXN0ZW5fbGFlbmdlbikKZXJzdGVzX3F1YXJ0aWwgPC0gcXVhbnRpbGUobGlzdGVuX2xhZW5nZW4sIDAuMjUpCm1lZGlhbl9saXN0ZW5fbGFlbmdlIDwtIG1lZGlhbihsaXN0ZW5fbGFlbmdlbikKZHJpdHRlc19xdWFydGlsIDwtIHF1YW50aWxlKGxpc3Rlbl9sYWVuZ2VuLCAwLjc1KQptYXhfbGlzdGVuX2xhZW5nZSA8LSBtYXgobGlzdGVuX2xhZW5nZW4pCgojIEF1c2dhYmUgZGVyIDUtWmFobGVuLVN0YXRpc3RpawpjYXQoIjUtWmFobGVuLVN0YXRpc3RpayBkZXIgTMOkbmdlbiBkZXIgVG9wLTIwIEVtcGZlaGx1bmdzbGlzdGVuOlxuIiwKICAgICJNaW5pbXVtOiIsIG1pbl9saXN0ZW5fbGFlbmdlLCAiXG4iLAogICAgIjEuIFF1YXJ0aWw6IiwgZXJzdGVzX3F1YXJ0aWwsICJcbiIsCiAgICAiTWVkaWFuOiIsIG1lZGlhbl9saXN0ZW5fbGFlbmdlLCAiXG4iLAogICAgIjMuIFF1YXJ0aWw6IiwgZHJpdHRlc19xdWFydGlsLCAiXG4iLAogICAgIk1heGltdW06IiwgbWF4X2xpc3Rlbl9sYWVuZ2UsICJcbiIpCmBgYAoKCiMjIyA3LjQuNCBWZXJ0ZWlsdW5nIGRlciBtaW5pbWFsZW4gQcyIaG5saWNoa2VpdCBmdcyIciBUb3AtTiBMaXN0ZW4gZnXMiHIgTiA9IDEwLCAyMCwgNTAsIDEwMCBmdcyIciBhbGxlIE51dHplciB2aXN1ZWxsIHZlcmdsZWljaGVuLgoKYGBge3J9CgpgYGAKCiMjIyA3LjQuNSBUb3AtMjAgRW1wZmVobHVuZ2VuIGZ1zIhyIE51dHplciDigJw14oCdLCDigJwyNeKAnSwg4oCcNTDigJ0sIOKAnDE1MOKAnSB2aXN1YWxpc2llcmVuCgpgYGB7cn0KCmBgYAoKIyMjIDcuNC42IEZ1zIhyIE51dHplciDigJwxMzPigJ0gdW5kIOKAnDU1NeKAnSBQcm9maWwgbWl0IFRvcC1OIEVtcGZlaGx1bmdlbiBmdcyIciBOID0gMjAsIDMwLCA0MCwgNTAgYW5hbHlzaWVyZW4sIHZpc3VhbGlzaWVyZW4gdW5kIGRpc2t1dGllcmVuCgpgYGB7cn0KCmBgYAoKIyMgVmVyd2VuZHVuZyB2b24gS0ktVG9vbHMKSW4gZGllc2VyIENoYWxsZW5nZSB3dXJkZSB0ZWlsd2Vpc2UgYXVmIEtJLVRvb2xzIHp1csO8Y2tnZWdyaWZmZW4uIERpZXNlIHNpbmQgaW0gRm9sZ2VuZGVuIGF1ZmdlbGlzdGV0OgpHaXRodWIgQ29waWxvdCB6dSB1bnRlcnN0w7x0enVuZyB2b24gc2NobmVsbGVyZW0gdW5kIGVmZml6aWVudGVyZW0gUHJvZ3JhbW1pZXJlbgpDaGF0LUdQVCB6dW0gZXJsw6R1dGVybiB2b24gS29uemVwdGVuIHVuZCB6dXIgSGlsZmUgZsO8ciBDb2RlIGdlbmVyaWVyZW4uCmA=